package com.dyz.leetcode;

public class NextPermutation31 {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if(n<=1){return;}

        int i= n-2; //n>2

        while (i>=0 && nums[i]>=nums[i+1]){
            i--;
        }

        if(i<0){
            reverse(nums, 0, n-1);
        }else {
            int j = n-1;
            while (i<j && nums[j]<=nums[i]){
                j--;
            }
            swap(nums, i, j);
            reverse(nums, i+1, n-1);
        }




    }

    private void reverse(int[] nums, int start, int end) {
        while (start<end){
            swap(nums,start,end);
            start++;
            end--;
        }

    }

    private void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
